/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package collections.maps;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;

/**
 *
 * @author Iaroslav_Mazai
 */
public class MyTreeMap implements MyMap {

	public class SimpleEntry implements MyMap.Entry {

		private Object key;
		private Object value;
		private SimpleEntry parent;
		private SimpleEntry leftChild;
		private SimpleEntry rightChild;
		private boolean isRed;

		@Override
		public Object getKey() {
			return key;
		}

		public void setKey(Object key) {
			this.key = key;
		}

		@Override
		public Object getValue() {
			return value;
		}

		@Override
		public Object setValue(Object value) {
			Object oldValue = getValue();
			this.value = value;
			return oldValue;
		}

		public SimpleEntry getParent() {
			return parent;
		}

		public void setParent(SimpleEntry parent) {
			this.parent = parent;
		}

		public SimpleEntry getLeftChild() {
			return leftChild;
		}

		public void setLeftChild(SimpleEntry leftChild) {
			this.leftChild = leftChild;
		}

		public SimpleEntry getRightChild() {
			return rightChild;
		}

		public void setRightChild(SimpleEntry rightChild) {
			this.rightChild = rightChild;
		}

		public SimpleEntry(Object key, Object value) {
			this.key = key;
			this.value = value;
			this.isRed = true;
		}

		public boolean isRed() {
			return isRed;
		}

		public boolean isBlack() {
			return !isRed;
		}

		public boolean isLeaf() {
			return (leftChild == null) && (rightChild == null);
		}

		public void setRed() {
			isRed = true;
		}

		public void setBlack() {
			isRed = false;
		}

		@Override
		public int hashcode() {
			return 3 * key.hashCode();
		}

		@Override
		public String toString() {
			String result = "<";
			result += (isRed ? "R" : "B") + "; ";
			result += key + "; ";
			if (parent != null) {
				result += parent.getKey() + ";";
				SimpleEntry left = parent.getLeftChild();
				SimpleEntry right = parent.getRightChild();
				if (left != null && compare(left.getKey(), this.getKey()) == 0) {
					result += "L;";
				}
				if (right != null && compare(right.getKey(), this.getKey()) == 0) {
					result += "R;";
				}

			} else {
				result += "null; ";
			}
			result += ">";

			result += "(" + key(getLeftChild()) + ";" + key(getRightChild()) + ")";
			return result;
		}
	}

	public SimpleEntry getRoot() {
		return root;
	}

	private static class DefaultComparator implements Comparator<Object> {

		@Override
		public int compare(Object o1, Object o2) {
			if (o1 == null) {
				return -1;
			}
			if (o2 == null) {
				return 1;
			}

			Comparable c1 = (Comparable) o1;
			Comparable c2 = (Comparable) o2;

			return c1.compareTo(c2);
		}
	}
	private SimpleEntry root;
	private Comparator comparator;
	private int size;

	public MyTreeMap() {
		this(new DefaultComparator());
	}

	public MyTreeMap(Comparator comparator) {
		root = null;
		size = 0;
		this.comparator = comparator;
	}

	@Override
	public void clear() {
		root = null;
	}

	private int compare(Object o1, Object o2) {
		return comparator.compare(o1, o2);
	}

	@Override
	public boolean containsKey(Object key) {
		SimpleEntry node = root;

		while (node != null) {
			if (compare(node.getKey(), key) == 0) {
				return true;
			}
			if (compare(node.getKey(), key) > 0) {
				node = node.getLeftChild();
			} else {
				node = node.getRightChild();
			}
		}

		return false;
	}

	private SimpleEntry findNodeWithKey(Object key) {
		SimpleEntry node = root;

		while (node != null) {
			if (compare(node.getKey(), key) == 0) {
				return node;
			}
			if (compare(node.getKey(), key) > 0) {
				node = node.getLeftChild();
			} else {
				node = node.getRightChild();
			}
		}

		return null;
	}

	@Override
	public Object get(Object key) {
		SimpleEntry node = findNodeWithKey(key);
		if (node != null) {
			return node.getValue();
		}
		return null;
	}

	@Override
	public boolean isEmpty() {
		return (size == 0);
	}

	@Override
	public Object put(Object key, Object value) {
		if (root == null) {
			root = new SimpleEntry(key, value);
			root.setBlack();
			size = 1;
			return null;
		}
		return putHelper(key, value, root);
	}

	public Object putHelper(Object key, Object value, SimpleEntry node) {

		if (compare(key, node.getKey()) == 0) {
			Object oldValue = node.getValue();
			node.setValue(value);
			return oldValue;
		}

		if (compare(key, node.getKey()) < 0) {
			if (node.getLeftChild() == null) {
				SimpleEntry newNode = new SimpleEntry(key, value);
				newNode.setParent(node);
				node.setLeftChild(newNode);
				size++;
				rearrangeOnPut(newNode);
				return null;
			} else {
				return putHelper(key, value, node.getLeftChild());
			}
		}

		if (compare(key, node.getKey()) > 0) {
			if (node.getRightChild() == null) {
				SimpleEntry newNode = new SimpleEntry(key, value);
				newNode.setParent(node);
				node.setRightChild(newNode);
				size++;
				rearrangeOnPut(newNode);
				return null;
			} else {
				return putHelper(key, value, node.getRightChild());
			}
		}

		return null;
	}

	private SimpleEntry getGrandParent(SimpleEntry node) {
		if (node == null) {
			return null;
		}

		if (node.getParent() == null) {
			return null;
		}

		return node.getParent().getParent();
	}

	private SimpleEntry getUncle(SimpleEntry node) {
		SimpleEntry grandParent = getGrandParent(node);
		if (grandParent == null) {
			return null;
		}
		if (getChildrenNumber(grandParent) < 2) {
			return null;
		}

		SimpleEntry leftParent = grandParent.getLeftChild();
		SimpleEntry rightParent = grandParent.getRightChild();

		if (compare(key(leftParent), key(node.getParent())) == 0) {
			return rightParent;
		} else {
			return leftParent;
		}
	}

	private Object key(SimpleEntry entry) {
		if (entry == null) {
			return null;
		} else {
			return entry.getKey();
		}
	}

	private void rotateRight(SimpleEntry node) {

		SimpleEntry oldQ = node;
		SimpleEntry oldP = oldQ.getLeftChild();
		SimpleEntry oldC = oldQ.getRightChild();

		SimpleEntry oldA = (oldP == null) ? null : oldP.getLeftChild();
		SimpleEntry oldB = (oldP == null) ? null : oldP.getRightChild();

		SimpleEntry parent = node.getParent();
		if (parent != null) {
			SimpleEntry left = parent.getLeftChild();
			SimpleEntry right = parent.getRightChild();
			if (compare(key(node), key(left)) == 0) {
				parent.setLeftChild(oldP);
			} else {
				parent.setRightChild(oldP);
			}
		} else {
			root = oldP;
		}
		oldP.setParent(parent);

		if (oldB != null) {
			oldB.setParent(oldQ);
		}
		oldQ.setLeftChild(oldB);

		oldP.setRightChild(oldQ);
		oldQ.setParent(oldP);
	}

	private void rotateLeft(SimpleEntry node) {

//		System.out.println("Rotating left: " + node);
//		System.out.println(this);
		SimpleEntry oldP = node;
		SimpleEntry oldA = oldP.getLeftChild();
		SimpleEntry oldQ = oldP.getRightChild();

		SimpleEntry oldB = (oldQ == null) ? null : oldQ.getLeftChild();
		SimpleEntry oldC = (oldQ == null) ? null : oldQ.getRightChild();

//		System.out.println("P: " + oldP);
//		System.out.println("Q: " + oldQ);
//		System.out.println("A: " + oldA);
//		System.out.println("B: " + oldB);
//		System.out.println("C: " + oldC);

		SimpleEntry parent = node.getParent();
		if (parent != null) {
			SimpleEntry left = parent.getLeftChild();
			SimpleEntry right = parent.getRightChild();
			if (compare(key(node), key(left)) == 0) {
				parent.setLeftChild(oldQ);
			} else {
				parent.setRightChild(oldQ);
			}
		} else {
			root = oldQ;
		}
		oldQ.setParent(parent);

		if (oldB != null) {
			oldB.setParent(oldP);
		}
		oldP.setRightChild(oldB);

		oldP.setParent(oldQ);
		oldQ.setLeftChild(oldP);

//			oldQ.setLeftChild(oldP);
//			oldP.setLeftChild(oldA);
//			oldP.setRightChild(oldB);
//
//			oldQ.setParent(parent);
//			oldP.setParent(oldQ);
//			oldC.setParent(oldQ);
//			oldA.setParent(oldP);
//			oldB.setParent(oldP);
//		System.out.println(this);
	}

	private void rearrangeOnPut(SimpleEntry node) {
		SimpleEntry uncle = getUncle(node);
		SimpleEntry grandParent = getGrandParent(node);

		firstRearrange(node, uncle, grandParent);
	}

	private void firstRearrange(SimpleEntry node, SimpleEntry uncle, SimpleEntry grandParent) {
//		System.out.println(node);
		if (node.getParent() == null) {
			node.setBlack();
//			System.out.println("1");
		} else {
			secondRearrange(node, uncle, grandParent);
		}
	}

	private void secondRearrange(SimpleEntry node, SimpleEntry uncle, SimpleEntry grandParent) {
		if (node.getParent().isBlack()) {
//			System.out.println("2");
		} else {
			thirdRearrange(node, uncle, grandParent);
		}
	}

	private void thirdRearrange(SimpleEntry node, SimpleEntry uncle, SimpleEntry grandParent) {
		if ((uncle != null) && (uncle.isRed())) {
//			System.out.println("3");
//			System.out.println("Parent: " + node.getParent());
//			System.out.println("Uncle: " + getUncle(node));
			node.getParent().setBlack();
			uncle.setBlack();
			grandParent.setRed();
			firstRearrange(grandParent, getUncle(grandParent), getGrandParent(grandParent));
		} else {
			fourthRearrange(node, uncle, grandParent);
		}
	}

	private void fourthRearrange(SimpleEntry node, SimpleEntry uncle, SimpleEntry grandParent) {
		if (compare(key(node), key(node.getParent().getRightChild())) == 0
			&& compare(key(node.getParent()), key(grandParent.getLeftChild())) == 0) {
//			System.out.println("4.1 (" + node.getParent() + ")");
			rotateLeft(node.getParent());
			node = node.getLeftChild();
		} else {
			if (compare(key(node), key(node.getParent().getLeftChild())) == 0
				&& compare(key(node.getParent()), key(grandParent.getRightChild())) == 0) {
//				System.out.println("4.2 (" + node.getParent() + ")");
				rotateRight(node.getParent());
				node = node.getRightChild();
			}
		}
		fifthRearrange(node, getUncle(node), getGrandParent(node));
	}

	private void fifthRearrange(SimpleEntry node, SimpleEntry uncle, SimpleEntry grandParent) {
		node.getParent().setBlack();
//		if (grandParent != root) {
		grandParent.setRed();
//		}
		if (compare(key(node), key(node.getParent().getLeftChild())) == 0) {
			rotateRight(grandParent);
//			System.out.println("5R");
		} else {
//			System.out.println(grandParent + " 5L");
			rotateLeft(grandParent);
//			System.out.println("5L");
		}
//		System.out.println("end 5");
	}

	private void change(SimpleEntry src, SimpleEntry newNode) {
		SimpleEntry parent = src.getParent();
		if (parent != null) {
			SimpleEntry left = parent.getLeftChild();
			SimpleEntry right = parent.getRightChild();
			if (compare(key(src), key(left)) == 0) {
				parent.setLeftChild(newNode);
			} else {
				parent.setRightChild(newNode);
			}
		}
		newNode.setParent(parent);
	}

	private int getChildrenNumber(SimpleEntry node) {
		int result = 0;
		if (node.getLeftChild() != null) {
			result++;
		}
		if (node.getRightChild() != null) {
			result++;
		}
		return result;
	}

	@Override
	public Object remove(Object key) {
		SimpleEntry node = findNodeWithKey(key);
		if (node == null) {
			return null;
		}
		Object oldValue = node.getValue();
		int childrenNumber = getChildrenNumber(node);

		SimpleEntry parent = node.getParent();
		SimpleEntry parentsLeftChild = parent.getLeftChild();
		SimpleEntry parentsRightChild = parent.getRightChild();
		Object leftKey = (parentsLeftChild != null) ? parentsLeftChild.getKey() : null;
		Object rightKey = (parentsRightChild != null) ? parentsRightChild.getKey() : null;
		boolean isNodeLeft = false;
		if (compare(key, leftKey) == 0) {
			isNodeLeft = true;
		}
		if (compare(key, rightKey) == 0) {
			isNodeLeft = false;
		}

		if (childrenNumber == 0) {
			if (isNodeLeft) {
				parent.setLeftChild(null);
			}
		}

		if (childrenNumber == 1) {
			SimpleEntry child;
			if (node.getLeftChild() != null) {
				child = node.getLeftChild();
			} else {
				child = node.getRightChild();
			}
			if (isNodeLeft) {
				parent.setLeftChild(child);
			} else {
				parent.setRightChild(child);
			}

		}

		if (childrenNumber == 2) {
			SimpleEntry child = getPredecessor(node);
			if (isNodeLeft) {
				parent.setLeftChild(child);
			} else {
				parent.setRightChild(child);
			}
		}

		size--;
		return oldValue;
	}

	private SimpleEntry getPredecessor(SimpleEntry node) {
		SimpleEntry currentNode = node.getLeftChild();
		while (currentNode.getRightChild() != null) {
			currentNode = currentNode.getRightChild();
		}
		return currentNode;
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public Iterator entryIterator() {
		throw new UnsupportedOperationException("Not supported yet.");
	}

	@Override
	public String toString() {
		String result = "Tree:\n";
		int i = 0;
		ArrayList nodes = new ArrayList();
		nodes.add(root);
		ArrayList newNodes = new ArrayList();

		while (i < size - 1) {
			newNodes = new ArrayList();
			for (Object entry : nodes) {
				result += entry;
			}
			result += "\n";
			for (Object object : nodes) {
				SimpleEntry entry = (SimpleEntry) object;
				if (entry.getLeftChild() != null) {
					newNodes.add(entry.getLeftChild());
					i++;
				}
				if (entry.getRightChild() != null) {
					newNodes.add(entry.getRightChild());
					i++;
				}
			}

			nodes = newNodes;
		}

		for (Object object : newNodes) {
			result += object;
		}

		return result;
	}
}
